package com.sise.Tree;

import java.util.HashMap;

/**
 *      105. 从前序与中序遍历序列构造二叉树
 *
 *      根据一棵树的前序遍历与中序遍历构造二叉树。
 *
 *      前序遍历 preorder = [3,9,20,15,7]       -       根左右
 *      中序遍历 inorder = [9,3,15,20,7]        -       左根右
 *      返回如下的二叉树：
 *
 *            3
 *           / \
 *          9  20
 *            /  \
 *           15   7
 *
 *      递归：
 *      1、终止条件： 数组的起始点 > 终止点，说明此事数组中没有元素了
 *      2、返回：返回已经构建好的子树
 *      3、本次递归所做动作：左子树的第一个节点为 根节点，通过此节点的值找到 中序遍历的根节点位置，然后得到 数组长度（因为是同一棵树），
 *                       得到长度后就可以进行切分子树
 */
public class _105_buildTree {

    private HashMap<Integer,Integer> indexMap = new HashMap<>();

    // 创建 value 与 索引下标 的映射
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        for (int i = 0; i < preorder.length; i++){
            indexMap.put(inorder[i], i);            // 这里放的是 inorder 的映射，不是 preorder
        }
        return myBuildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);   // 这里末尾长度要 n - 1，因为数组长度从 0 开始
    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight){
        if (preLeft > preRight) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preLeft]);            // 前序遍历的第一个节点就是根节点
        Integer inorderIndex = indexMap.get(preorder[preLeft]);     // 从 Map 中确认根节点的 索引位置
        int sizeLeftSubtree = inorderIndex - inLeft;               // 得到左子树中的节点数目，由于同一颗子树的前序遍历和中序遍历的长度是相同的，故此利用差距算出 数组分割位置

        // left: [pre, inorder, [1] = 9, [2] = 20, [0] = 9, [1] = 3]，其中两个数组依旧往下传递，左右子树的索引下标也向下传递
        root.left = myBuildTree(preorder, inorder, preLeft + 1, preLeft + sizeLeftSubtree, inLeft, inorderIndex - 1);
        root.right = myBuildTree(preorder, inorder, preLeft + sizeLeftSubtree + 1, preRight, inorderIndex + 1, inRight);
        return root;
    }
}
